package br.ufmg.vod.wbr.algorithims.bfs;

import br.ufmg.vod.collections.IntQueue;
import br.ufmg.vod.collections.IntQueueStack;
import br.ufmg.vod.wbr.api.Graph;

public class FastBFS implements BFS{
	

	private BFSData data;
	private IntQueue queue;
	
	public FastBFS(Graph g) {
		this.queue = new IntQueueStack(g.getNumVertex());
		this.data = new BFSData(g);
	}
	

	@Override
	public BFSData bfsAllVertex() {
		for (int i = 0; i < this.data.graph.getNumVertex(); i++) {
			if(this.data.colors[i] == BFSData.WHITE )
				this.bfsSingleVertex(i);
		}
		return this.getData();
	}

	@Override
	public BFSData bfsSingleVertex(int u) {
		
		if(this.data.colors[u] != BFSData.WHITE ){ 
			throw new RuntimeException("ALREADY VISITED "+u+"!");
		}
		
		this.queue.clear();
		this.data.dist[u]=0;
		this.data.predecessor[u]=u;
		this.data.colors[u] = BFSData.GRAY;
		this.queue.enqueue(u);
		
		while(!this.queue.isEmpty()){
			u = this.queue.dequeue();
			this.data.discoveryTime[u] = ++this.data.time;
			int[] neighbours = this.data.graph.getEdges(u);

			
			for (int i = 0; i < neighbours.length; i++) {
				int v = neighbours[i];
				if( this.data.colors[v] == BFSData.WHITE ){
					this.data.dist[v]=this.data.dist[u]+1;
					this.data.maxDist = Math.max(this.data.maxDist, this.data.dist[v]);
					this.data.avgDist = (this.data.avgDist*this.data.minPathCount + this.data.dist[v])/++this.data.minPathCount; 
					this.data.predecessor[v]=u;
					this.data.colors[v] = BFSData.GRAY;
					this.queue.enqueue(v);
				}
			}
			
			this.data.closeTime[u] = this.data.time;
			this.data.colors[u] = BFSData.BLACK;
			this.data.visitedQueue.enqueue(u);
		}
		return this.getData();
	}

	@Override
	public BFSData getData() {
		return data;
	}

	@Override
	public void run() {
		this.bfsAllVertex();
	}


	@Override
	public void clear() {
		this.data.clearVisitedData();
	}
	


}
